#pragma once
#pragma warning(disable: 4290)

#include "utility.h"
#include <initializer_list>
#include <exception>

namespace qyc
{
	template<class T>
	struct forward_list_node
	{
	private:
		typedef T data_type;
		typedef forward_list_node<data_type> self;
		typedef self* self_pointer;
	public:
		explicit forward_list_node(const data_type& data)
			: _data(data)
		{}
		explicit forward_list_node(data_type&& data = data_type())
			: _data(qyc::forward<data_type>(data))
		{}
		template <class... Args>
		forward_list_node(Args&&... args)
			: _data(args...)
		{}

		void swap(self& right)
		{
			qyc::swap(_data, right._data);
			qyc::swap(_next, right._next);
		}

		data_type _data = data_type();
		self_pointer _next = nullptr;
	};

	template<class T>	class forward_list;

	template<class T>
	struct __forward_list_const_iterator
	{
		typedef T data_type;
		typedef const data_type& reference_type;
		typedef const data_type* pointer_type;
	private:
		typedef forward_list_node<data_type> Node;
		typedef Node* NodePtr;
		typedef __forward_list_const_iterator<data_type> self;

		friend class forward_list<data_type>;

		NodePtr _node = nullptr;
	public:
		__forward_list_const_iterator(NodePtr node = nullptr)
			: _node(node)
		{}

		reference_type operator*() const {
			return _node->_data;
		}
		pointer_type operator->() const {
			return &(_node->_data);
		}

		bool operator==(const self& it) const {
			return (_node == it._node);
		}
		bool operator!=(const self& it) const {
			return (_node != it._node);
		}

		self& operator++() {
			_node = _node->_next;
			return *this;
		}
		self operator++(int) {
			self ret = _node;
			_node = _node->_next;
			return ret;
		}

		void swap(self& it) {
			qyc::swap(_node, it._node);
		}
	};

	template<class T>
	struct __forward_list_iterator : public __forward_list_const_iterator<T>
	{
		typedef T data_type;
		typedef data_type& reference_type;
		typedef data_type* pointer_type;
	private:
		typedef forward_list_node<data_type> Node;
		typedef Node* NodePtr;
		typedef __forward_list_iterator<data_type> self;
		typedef __forward_list_const_iterator<data_type> base_class;

		friend class forward_list<data_type>;
	public:
		__forward_list_iterator(NodePtr node = nullptr)
			: base_class(node)
		{}

		reference_type operator*() const {
			return const_cast<reference_type>(base_class::operator*());
		}
		pointer_type operator->() const {
			return &(operator*());
		}

		self& operator++() {
			base_class::operator++();
			return *this;
		}
		self operator++(int) {
			self ret = *this;
			base_class::operator++();
			return ret;
		}
	};

	template<class T>
	class forward_list
	{
		typedef T data_type;
		typedef data_type& reference;
		typedef const data_type& const_reference;
		typedef data_type* pointer;
		typedef const data_type* const_pointer;

		typedef forward_list_node<data_type> Node;
		typedef Node* NodePtr;
		typedef forward_list<data_type> self;

		void empty_initialize()
		{
			_pHead = new Node;
			_pHead->_next = _pHead;
		}
	public:
		typedef __forward_list_iterator<data_type> iterator;
		typedef __forward_list_const_iterator<data_type> const_iterator;

		forward_list()
		{
			empty_initialize();
		}
		forward_list(const self& right)
		{
			empty_initialize();
			_pHead->_next = copy(right._pHead, _pHead);
			if (_pHead->_next == nullptr)
				_pHead->_next = _pHead;
		}
		forward_list(self&& right)
		{
			empty_initialize();
			qyc::swap(_pHead, right._pHead);
		}
		self& operator=(const self& right)
		{
			if (&right != this)
			{
				clear();
				insert_after(begin(), right.begin(), right.end());
			}
			return *this;
		}
		self& operator=(self&& right)
		{
			swap(right);
			return *this;
		}

		forward_list(size_t n, const data_type& data)
		{
			empty_initialize();
			for (; n > 0; --n)
				push_front(data);
		}
		forward_list(int n, const data_type& data)
		{
			new(this)self(static_cast<size_t>(n), data);
		}
		forward_list(long n, const data_type& data)
		{
			new(this)self(static_cast<size_t>(n), data);
		}
		explicit forward_list(size_t n)
		{
			new(this)self(n, data_type());
		}
		template<class InputIterator>
		forward_list(InputIterator first, InputIterator last)
		{
			empty_initialize();
			insert_after(end(), first, last);
		}
		forward_list(std::initializer_list<data_type> _Ilist)
		{
			new(this)self(_Ilist.begin(), _Ilist.end());
		}

		iterator begin()
		{
			return _pHead->_next;
		}
		iterator end()
		{
			return _pHead;
		}
		iterator before_begin()
		{
			return end();
		}
		const_iterator begin() const
		{
			return _pHead->_next;
		}
		const_iterator end() const
		{
			return _pHead;
		}
		const_iterator before_begin() const
		{
			return end();
		}

		template <class... Args>
		void emplace_front(Args&&... args)
		{
			emplace_after(before_begin(), args...);
		}
		void push_front(const data_type& data)
		{
			emplace_front(data);
		}
		void push_front(data_type&& data)
		{
			emplace_front(qyc::forward<data_type>(data));
		}
		void pop_front()
		{
			if (empty())
				return;
			NodePtr del = _pHead->_next;
			_pHead->_next = del->_next;
			delete del;
		}

		template <class... Args>
		iterator emplace_after(iterator pos, Args&&... args)
		{
			NodePtr node = new Node(args...);
			node->_next = pos._node->_next;
			pos._node->_next = node;
			return node;
		}
		iterator insert_after(iterator pos, const data_type& data)
		{
			return emplace_after(pos, data);
		}
		iterator insert_after(iterator pos, data_type&& data)
		{
			return emplace_after(pos, qyc::forward<data_type>(data));
		}
		iterator insert_after(iterator pos, int n, const data_type& val)
		{
			insert_after(pos, static_cast<size_t>(n), val);
		}
		iterator insert_after(iterator pos, long n, const data_type& val)
		{
			insert_after(pos, static_cast<size_t>(n), val);
		}
		iterator insert_after(iterator pos, size_t n, const data_type& val)
		{
			while (n--)
				pos = insert_after(pos, val);
			return pos;
		}
		template <class InputIterator> 
		iterator insert_after(iterator pos, InputIterator first, InputIterator last)
		{
			while (first != last)
			{
				pos = insert_after(pos, *first);
				++first;
			}
			return pos;
		}
		
		iterator erase_after(iterator pos)
		{
			if (empty())
				return end();
			NodePtr node = pos._node->_next;
			pos._node->_next = node->_next;
			delete node;
			return ++pos;
		}
		iterator erase_after(iterator pos, iterator last)
		{
			while (pos != last)
			{
				if (erase_after(pos) == end())
					return end();
			}
			return pos;
		}

		void resize(size_t n)
		{
			resize(n, data_type());
		}
		void resize(size_t n, const data_type& data)
		{
			iterator first = begin(), prev = begin();
			size_t len = 0;
			for (; len < n && first != end(); ++first, ++len)
				prev = first;
			if (len < n)
				insert_after(prev, n - len, data);
			else
				erase_after(first, end());
		}
		reference front() throw(std::out_of_range)
		{
			if (empty())
				throw std::out_of_range("err: forward_list:: empty()");
			return _pHead->_next->_data;
		}
		const_reference front() const throw(std::out_of_range)
		{
			if (empty())
				throw std::out_of_range("err: forward_list:: empty()");
			return _pHead->_next->_data;
		}
		bool empty() const
		{
			return (_pHead->_next == _pHead);
		}
		void reverse()
		{
			NodePtr prev = _pHead;
			NodePtr cur = _pHead->_next;
			while (cur != _pHead) {
				NodePtr next = cur->_next;
				cur->_next = prev;
				prev = cur;
				cur = next;
			}
			_pHead->_next = prev;
		}
		void clear()
		{
			if (empty())
				return;
			NodePtr prev = _pHead->_next;
			for (NodePtr cur = prev->_next; cur != _pHead; cur = cur->_next)
			{
				delete prev;
				prev = cur;
			}
			delete prev;
			_pHead->_next = _pHead;
		}
		void swap(self& right)
		{
			qyc::swap(_pHead, right._pHead);
		}
		~forward_list()
		{
			clear();
			delete _pHead;
			_pHead = nullptr;
		}
	private:
		NodePtr copy(NodePtr pHead, NodePtr tail)
		{
			NodePtr ret = nullptr, prev = nullptr;
			for (NodePtr cur = pHead->_next; cur != pHead; cur = cur->_next)
			{
				NodePtr tmp = new Node(cur->_data);
				if (ret == nullptr)
					ret = tmp;

				if (prev != nullptr)
					prev->_next = tmp;
				prev = tmp;
			}
			if (prev != nullptr)
				prev->_next = tail;
			return ret;
		}

		NodePtr _pHead = nullptr;
	};
}